def exchange(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    left = 0
    right = len(nums) - 1
    while left < right:
        if nums[left] % 2 == 0 and nums[right] % 2 == 1:  # 左偶右奇
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        elif nums[left] % 2 == 0 and nums[right] % 2 == 0:  # 左右都偶
            right -= 1
        else:
            left += 1
    return nums


print(exchange([2, 16, 3, 5, 13, 1, 16, 1, 12, 18, 11, 8, 11, 11, 5, 1]))